import java.util.Arrays;

/**
 * 归并排序
 * 实现思路：分治法
 * 自上而下递归完成
 */
public class MergeSort {
    public static int[] res;

    public static int[] mergeSort(int[] nums) {
        int len = nums.length;
        res = Arrays.copyOf(nums, len);
        merge(0, len - 1);
        return res;
    }

    public static void merge(int start, int end) {
        if (start >= end) {
            // 没有或者只有一个元素时，不需要排序
            return;
        }
        // 二分
        int mid = start + (end - start) / 2;
        // 分解为左右两部分，对两部分递归完成排序
        merge(start, mid);
        merge(mid + 1, end);
        // 剪枝，两部分已经有序（左边最大值小于等于右边最小值）
        if (res[mid] <= res[mid + 1]) {
            return;
        }
        int i = 0;
        int[] tempArr = new int[end - start + 1];
        int left = start, right = mid + 1;

        // [left, mid]，[mid + 1, right] 两部分的元素，有序地记录到 cur 数组中
        while (left <= mid && right <= end) {
            if (res[left] <= res[right]) {
                tempArr[i] = res[left];
                left ++;
            } else {
                tempArr[i] = res[right];
                right ++;
            }
            i ++;
        }
        // 左侧部分的剩余元素（剩左则不剩右）
        while (left <= mid) {
            tempArr[i] = res[left];
            left ++;
            i ++;
        }
        // 右侧部分的剩余元素（剩右则不剩左）
        while (right <= end) {
            tempArr[i] = res[right];
            right ++;
            i ++;
        }
        // 将完成排序的 tempArr 数组中的元素依次放回到 res 数组的 [left, right] 中
        for (int j = start; j <= end; j++) {
            res[j] = tempArr[j - start];
        }
    }
}
